public class class01 {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
//        1.一个为空，一个不为空，不相同---结构上不同
        if (p==null && q!=null || p!=null && q==null){
            return false;
        }
//        2.两个都为空，是相同的树
        if (p==null && q==null){
            return true;
        }
//        3.两个都不为空，值不同，也是不同的
        if (p!=null && q!=null && p.val != q.val){
            return false;
        }
//        上述代码完成，证明走到这里 p！=null && q！= null && 根结点值一样
//          两个根节点都不为空且值一样，同一棵树！
//          p的左子树与q的左子树相同，p的右子树与q的右子树相同
//        if (p!=null && q!=null && p.val== q.val){  不行的
//            return true;
//        }

        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null){
            return false;
        }
//        先判断根结点，是不是两颗相同的树
        if (isSameTree(root,subRoot)){
            return true;
        }
//        如果不一样，那就判断subRoot是不是root左树的子树
        if (isSubtree(root.left,subRoot)){
            return true;
        }
        if (isSameTree(root.right,subRoot)){
            return true;
        }
       return  false;
    }

    public TreeNode invertTree(TreeNode root) {
        if (root == null){
            return null;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}
